package com.shangguigu.stack;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/11
 * @description: 用单链表实现栈 入栈：将元素加入到head
 * 出栈：将元素从头节点释放
 */
public class SinglyLinkedListStack implements MyStack {

	/**
	 * 最大容量(链表就不设置最大容量了)-->还是用最大容量限制一下
	 */
	private int maxSize;
	/**
	 * 头节点
	 */
	private ListNode head;
	/**
	 * 虚拟节点
	 */
	private ListNode dummy;
	/**
	 * 当前容量
	 */
	private int size;


	public SinglyLinkedListStack(int maxSize) {
		dummy=new ListNode(-1);
		size=0;
		this.maxSize=maxSize;
	}

	@Override
	public boolean isFull() {
		return size==maxSize;
	}

	@Override
	public boolean isEmpty() {
		return head==null;
	}

	@Override
	public void push(int value) {
		if (isFull()){
			return;
		}else{
			///1.生成节点
			ListNode node = new ListNode(value);
			///2.让虚拟节点指向新节点
			dummy.next=node;
			///3.让新节点指向头节点
			node.next=head;
			///4.重置头节点
			head=node;
			size++;
		}
	}

	@Override
	public int pop() {
		if (isEmpty()){
			return -1;
		}else {
			int val = dummy.next.val;
			dummy.next=head.next;
			head=dummy.next;
			size--;
			return val;
		}
	}

	/**
	 * 从栈顶遍历！
	 */
	@Override
	public void list() {
		ListNode cur=dummy.next;
		while (cur!=null){
			System.out.printf("%d \t",cur.val);
			cur=cur.next;
		}
	}

	public static void main(String[] args) {
		MyStack stack = new SinglyLinkedListStack(4);
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(5);

		stack.list();

		stack.pop();

		stack.list();
	}
}
